package cn.com.mdx.search;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author huangyuan
 * @date 2020/6/29
 * @description 二分查找练习
 */
public class BinarySearchPractice {

    /**
     * 练习问题：给定数组没有重复元素，且符合先递增后递减的条件
     * 例如：[1,2,8,13,24,36,39,42,68,17,5,-7,-132]
     *
     * @param array    要查找的数组
     * @param value    要查找的值
     * @param startPos 起始位置
     * @param endPos   结束位置
     * @return int 元素位置在数组中的位置，未找到返回-1
     * @methodName searchInArrayIncrementAfterDiminishing
     * @Desc 在先递增后递减的数组中查找元素
     * @Author huangyuan
     * @Date 2020/6/29 4:50 下午
     */
    public static int searchInArrayDiminishingAfterIncrement(int[] array, int value, int startPos, int endPos) {
        if (array == null || array.length < 3) throw new IllegalArgumentException("传递数组长度不合法");
        //获取中间位置
        int mid = (startPos + endPos) >>> 1;
        //边缘检测
        if (mid == startPos || mid == endPos) if (array[mid] == value) return mid;
        //查看中间位置所在数组中的位置
        int result;
        //1.最大值
        if (array[mid] > array[mid - 1] && array[mid] > array[mid + 1]) {
            //通过两次二分查找
            //正序二分
            result = BinarySearch.binarySearchFromPart(array, value, startPos, mid);
            if (result > -1) return result;
            //逆序二分
            result = BinarySearch.binarySearchFromPartDesc(array, value, mid + 1, endPos);
            if (result > -1) return result;
        }
        //2.处于递增序列
        else if (array[mid] > array[mid - 1] && array[mid] < array[mid + 1]) {
            if (value < array[mid]) {
                //左半部分通过正序二分查找
                result = BinarySearch.binarySearchFromPart(array, value, startPos, mid - 1);
                if (result > -1) return result;
            } else
                //右半部分通过迭代继续查找
                return searchInArrayDiminishingAfterIncrement(array, value, mid, endPos);
        }
        //3.处于递减序列
        else {
            if (value < array[mid]) {
                //右半部分通过逆序二分查找
                result = BinarySearch.binarySearchFromPartDesc(array, value, mid + 1, endPos);
                if (result > -1) return result;
            } else
                //左半部分通过迭代继续查找
                return searchInArrayDiminishingAfterIncrement(array, value, startPos, mid);
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] array = {33, 41, 31, 10, 0};
        System.out.println("查找1的结果：" + searchInArrayDiminishingAfterIncrement(array, 32,
                0, array.length - 1));
        System.out.println("查找-1000的结果：" + searchInArrayDiminishingAfterIncrement(array, -1000,
                0, array.length - 1));
    }

}
